package graph.digraph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 检测有向图是否有环
 */
public class DirectedCycle {
    // 标记遍历过的点
    private boolean[] marked;
    // 是否有环
    private boolean hasCycle;
    // 记录当前顶点有没有已经处于正在搜搜的有向路径上
    private boolean[] onStack;

    public DirectedCycle(Digraph G) {
        marked = new boolean[G.V()];
        onStack = new boolean[G.V()];
        hasCycle = false;

        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                // 对每个顶点进行深度搜索
                dfs(G, v);
            }
        }
    }

    /**
     * 基于深度优先搜索
     */
    private void dfs(Digraph G, int v) {
        // 当前顶点已搜索
        marked[v] = true;
        // 当前顶点进栈
        onStack[v] = true;

        // 遍历当前顶点邻接表
        for (Integer w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
            if (onStack[w]) {
                hasCycle = true;
                return;
            }
        }
        // 出栈
        onStack[v] = false;

    }

    public boolean hasCycle() {
        return hasCycle;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(DirectedCycle.class.getClassLoader().getResourceAsStream("road_find.txt")));
        int number = Integer.parseInt(reader.readLine());
        Digraph G = new Digraph(number);
        int roadNumber = Integer.parseInt(reader.readLine());
        // 循环读取道路，并调用addEdge方法
        for (int i = 0; i < roadNumber; i++) {
            String line = reader.readLine();
            int p = Integer.parseInt(line.split(" ")[0]);
            int q = Integer.parseInt(line.split(" ")[1]);
            G.addEdge(p, q);
        }
        // 创建测试对象
        DirectedCycle directedCycle = new DirectedCycle(G);
        System.out.println(directedCycle.hasCycle());
    }

}
